Upon transmitting an information signal from a transmitter to a receiver via a channel, the information signal may be transmitted as error information due to channel distortion and the influence of noise and so on.
To reduce such errors, the transmitter performs coding processing and the receiver performs decoding processing. Here, as a code that can be processed in a relatively simple manner and that enables efficient error correction, a convolutional code is known in particular.
FIG. 1 illustrates a configuration example of a convolutional encoder. The constraint length K of the convolutional encoder shown in FIG. 1 is 7, and this encoder assumes 2K−1=26 possible transition states.
Here, “termination” and “tail-biting” are known as a method of dividing an information signal sequence into a plurality of coding blocks each comprised of a predetermined number of bits and transmitting these coding blocks individually.
The termination method assumes that the initial state of the encoder is known (generally, a signal sequence comprised of K−1 zero-value signals). This is equivalent to attaching a known signal to the heads of the above-noted coding blocks that are inputted in the encoder. Further, the termination method attaches a known signal (which is generally a signal sequence comprised of K−1 zero-value signals) to the tail ends of the above-noted coding blocks inputted in the encoder, so that it is possible to uniquely determine the state of the encoder at the time when coding processing of the coding blocks inputted in the encoder is finished. Therefore, if the decoder knows the above-noted known signals in advance, the decoder can identify the initial state and the end state corresponding to the coding blocks included in the received signal.
On the other hand, the tail-biting method assumes that a sequence comprised of the initial values of a plurality of registers included in the encoder is the same as the signal sequence which is comprised of K−1 signals and attached to the tail ends of coding blocks. By this means, the initial state and the end state of the encoder are the same. However, unlike the termination method, the initial state (end state) is not always fixed, and, consequently, the decoder cannot predict in which state the initial state (end state) is.
Here, the state transition of a convolutional encoder is represented by a trellis diagram. In the case of the tail-biting method, the initial state and the end state of an encoder are the same, and, consequently, the trellis diagram is assumed to be cyclic as shown in FIG. 2.
As suboptimal maximum-likelihood decoding of the convolutional code described above, the Viterbi algorithm is widely known.
This Viterbi algorithm will be explained below. Further, S0, S1, . . . , SL−1 are used as the states of an encoder. Further, in the trellis diagram, if there is a branch from the state Si (i=0, . . . , M−1) at point t to the state Sj (j=0, . . . , L−1) at point t+1, this branch is represented by bij. Further, paths that survive and connect between states at points in the trellis diagram will be referred to as “surviving paths.” Further, the surviving path to the state Si at point t is represented by pi,t and the metric of the surviving path is represented by λi,t.
In this case, the basic operations of the Viterbi algorithm will be described as follows.
(1) In the trellis diagram, with respect to received sequence yt, the branch metrics λ(yt, bij) of all branches bij from state Si at point t to state Sj at point t+1 are calculated. (2) The branch metrics λ(yt, bij) of all branches bij and the metrics λi,t of surviving paths pi,t of the state Si at point t connecting to branches bij, are added. (3) The sums calculated in (2) about all paths connecting to the state Sj at point t+1 are compared, and the combination of the surviving path pi,t and branch bij are found where the sum is minimum. Here, the path connecting pi,t and bij is the surviving path pj, t+1 of Si. Further, the surviving path metric pj, t+1 of the surviving path pj, t+1 of Si is calculated by λi,t+λ(yt, bij). The above-noted processing in (3) is performed for all of states Sj at point t+1.
Here, the above-described addition in (2) and the above-described comparison of metrics and calculations to select a path where a minimum value is acquired in (3), are collectively referred to as “ACS (Add Compare Select) calculation.”
Next, when the ACS calculation is finished, it is possible to acquire the decoding result by tracing back the surviving paths. This processing of tracing the surviving paths is called “traceback.”
Here, generally, a codeword transmitted by the tail-biting method requires a greater amount of calculations and longer processing time on the receiving side than a codeword transmitted by the termination method. This is because, as described above, the decoder cannot predict the initial state (end state) by the tail-biting method.
Therefore, upon adopting the tail-biting method, the decoder is demanded to reduce the amount of processing.
Next, a conventional decoding method for a convolutional codeword transmitted by the tail-biting method will be explained.
Non-Patent Document 1 discloses performing the decoding processing shown in FIG. 3. To be more specific, the construction of trellis diagram by ACS calculation is repeated a plurality of times (three times in FIG. 3) with respect to coding block 0 (“TB block 0” in FIG. 3), which is a received packet. Here, upon consecutively repeating ACS calculation with respect to a received packet, a feature of the tail-biting is utilized that the initial state and the end state of an encoder are the same.
Further, a traceback is performed for the trellis diagram acquired by repeating the ACS calculation a plurality of times. In this traceback, a training period is provided. Although training is the same as traceback in tracking back the surviving paths, the training differs from traceback in not using the tracking result as a decoding result (i.e., in not outputting the tracking result as a decoding result).
After this training processing, traceback processing is performed, and the processing result is used (outputted) as a decoding result.
Further, Non-Patent document 2, Non-Patent Document 3 and Patent Document 1 disclose performing the processing shown in FIG. 4. To be more specific, a tail-biting check is performed at every timing ACS calculation is performed one time for a received packet (i.e. one loop of coding block length). The tail-biting check refers to the processing of tracking surviving paths like a traceback and checking whether the initial state and the end state match. Here, according to the result of the tail-biting check, the decoding result is outputted if the initial state and the end state match, and the ACS calculation is repeated if the initial state and the end state do not match.
Thus, conventional Viterbi decoding processing utilizes the feature that the initial state and the end state of an encoder adopting the tail-biting method are equivalent, thereby performing decoding processing of a received packet using received packet as the ACS calculation repeating unit.